﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GraphTheory.Task1
{
    class PureGraph
    {
        private int[] Vertices;
        private int[,] AdjacencyMatrix;

        public PureGraph(int[] Vertices, int[,] AdjacencyMatrix)
        {
            this.Vertices = Vertices;
            this.AdjacencyMatrix = AdjacencyMatrix;
        }

        public PureGraph(int VerticesAmount, int[,] AdjacencyMatrix)
        {
            this.Vertices = new int[VerticesAmount];
            for (int i = 0; i < VerticesAmount; i++)
            {
                this.Vertices[i] = i;
            }
            this.AdjacencyMatrix = AdjacencyMatrix;
        }

        public static PureGraph ParseFromString(string str)
        {
            StringScanner scanner = new StringScanner(str);
            int Vertices = scanner.nextInt();
            int[,] AdjacencyMatrix = new int[Vertices, Vertices];

            for (int i = 0; i < Vertices; i++)
            {
                for (int j = 0; j < Vertices; j++)
                {
                    AdjacencyMatrix[i, j] = scanner.nextInt();
                }
            }
            return new PureGraph(Vertices, AdjacencyMatrix);
        }

        public bool IsEmpty()
        {
            return Vertices.Length == 0;
        }


        public static int FindAdjacentAbsorptive(PureGraph graph)
        {
            foreach (var vrt in graph.Vertices)
            {
                bool isSo = false;
                foreach (var vrt1 in GetAdjacencyList(graph, vrt))
                {
                    foreach (var vrt2 in GetAdjacencyList(graph, vrt1))
                    {
                        isSo = (vrt2 == vrt || graph.AreAdjacent(vrt, vrt2));
                        if (!isSo)
                        {
                            break;
                        }
                    }
                    if (isSo)
                    {
                        return vrt;
                    }
                }
            }
            return -1;
        }

        public static int[] GetBiggestIndependencySet(PureGraph graph)
        {
            PureGraph graphCopy = graph.GetCopy();
            int adjacentAbsorptiveVrt = FindAdjacentAbsorptive(graphCopy);
            while (adjacentAbsorptiveVrt >= 0)
            {
                graphCopy.DeleteVertex(adjacentAbsorptiveVrt);
                adjacentAbsorptiveVrt = FindAdjacentAbsorptive(graphCopy);
            }
            return graphCopy.Vertices;
        }

        public static List<int> GetAdjacencyList(PureGraph graph, int vrt)
        {
            List<int> res = new List<int>();
            foreach (var vrt1 in graph.Vertices)
            {
                if (graph.AreAdjacent(vrt, vrt1))
                {
                    res.Add(vrt1);
                }
            }
            return res;
        }
        
        public bool AreAdjacent(int vrt1, int vrt2)
        {
            return this.AdjacencyMatrix[GetIndex(this.Vertices, vrt1), GetIndex(this.Vertices, vrt2)] > 0;
        }

        public void AddEdge(int vrt1, int vrt2)
        {
            int index1 = GetIndex(this.Vertices, vrt1);
            int index2 = GetIndex(this.Vertices, vrt2);
            this.AdjacencyMatrix[index1, index2] = 1;
            this.AdjacencyMatrix[index2, index1] = 1;
        }
        

        public void DeleteVertex(int vrt)
        {
            int index = GetIndex(this.Vertices, vrt);
            List<int> vrts = this.Vertices.ToList();
            vrts.Remove(vrt);
            int[,] newAdjacencyMatrix = new int[vrts.Count(), vrts.Count()];

            for (int i = 0; i < vrts.Count(); i++)
            {
                for (int j = 0; j < vrts.Count(); j++)
                {
                    if (i < index && j < index)
                    {
                        newAdjacencyMatrix[i, j] = this.AdjacencyMatrix[i, j];
                    }
                    else if (i >= index && j < index)
                    {
                        newAdjacencyMatrix[i, j] = this.AdjacencyMatrix[i + 1, j];
                    }
                    else if (i < index && j >= index)
                    {
                        newAdjacencyMatrix[i, j] = this.AdjacencyMatrix[i, j + 1];
                    }
                    else if (i >= index && j >= index)
                    {
                        newAdjacencyMatrix[i, j] = this.AdjacencyMatrix[i + 1, j + 1];
                    }
                }

            }
            
            this.Vertices = vrts.ToArray();
            this.AdjacencyMatrix = newAdjacencyMatrix;
        }
                
        public void DeleteEdge(int vrt1, int vrt2)
        {
            this.AdjacencyMatrix[GetIndex(this.Vertices, vrt1), GetIndex(this.Vertices, vrt2)] = 0;
            this.AdjacencyMatrix[GetIndex(this.Vertices, vrt2), GetIndex(this.Vertices, vrt1)] = 0;
        }

        private static int GetIndex(int[] Vertices, int vrt)
        {
            for(int i = 0; i < Vertices.Length; i++)
            {
                if(Vertices[i] == vrt)
                {
                    return i;
                }
            }
            throw new ArgumentException();
        }

        public PureGraph GetCopy()
        {
            int[,] AdjacencyMatrixCopy = new int[this.Vertices.Length, this.Vertices.Length];
            for (int i = 0; i < this.Vertices.Length; i++)
            {
                for (int j = 0; j < this.Vertices.Length; j++)
                {
                    AdjacencyMatrixCopy[i, j] = this.AdjacencyMatrix[i, j];
                }
            }

            int[] VerticesCopy = new int[this.Vertices.Length];
            for (int i = 0; i < this.Vertices.Length; i++)
            {
                VerticesCopy[i] = this.Vertices[i];
            }

            return new PureGraph(VerticesCopy, AdjacencyMatrixCopy);
        }
        
        public override string ToString()
        {
            string res = "";
            for (int i = 0; i < this.Vertices.Length; i++)
            {
                for (int j = 0; j < this.Vertices.Length; j++)
                {
                    res += " " + AdjacencyMatrix[i, j];
                }
                res += "\n";
            }
            return res;
        }
    }
    
}
